package org.czx.datactruct.eight;

/**
 * @author czx
 * @date 2020/9/24 15:10
 */
public class LinkedGroup<T extends Comparable<? super T>> {
    private Node firstNode;
    int length;

    public void insertionSort() {
        // If fewer than two items are in the chain, there is nothing to do
        if (length > 1) {
            assert firstNode != null;
            // Break chain into 2 pieces: sorted and unsorted
            Node unsortedPart = firstNode.getNextNode();
            assert unsortedPart != null;
            firstNode.setNextNode(null);

            while (unsortedPart != null) {
                Node nodeToInsert = unsortedPart;
                unsortedPart = unsortedPart.getNextNode();
                insertInOrder(nodeToInsert);
            }
        }
    }

    private void insertInOrder(Node nodeToInsert) {
        T item = nodeToInsert.getData();
        Node currentNode = firstNode;
        Node previousNode = null;  //当前位置的前一个节点，要插入时需要将前一节点的next指针修改掉

        //Locate insertion point
        while (currentNode != null && (item.compareTo(currentNode.getData()) > 0)) {
            previousNode = currentNode;
            currentNode = currentNode.getNextNode();
        }

        // Make the insertion
        if (previousNode != null) {
            previousNode.setNextNode(nodeToInsert);
            nodeToInsert.setNextNode(currentNode);
        } else // Insert at beginning
        {
            nodeToInsert.setNextNode(firstNode);
            firstNode = nodeToInsert;
        }
    }

    private class Node {
        private T data;  // Entry in bag
        private Node next;  // Link to next node

        private Node(T dataPortion) {
            this(dataPortion, null);
        } // end constructor

        private Node(T dataPortion, Node nextNode) {
            data = dataPortion;
            next = nextNode;
        } // end constructor

        private T getData() {
            return data;
        } // end getData

        private void setData(T newData) {
            data = newData;
        } // end setData

        private Node getNextNode() {
            return next;
        } // end getNextNode

        private void setNextNode(Node nextNode) {
            next = nextNode;
        } // end setNextNode
    }
}
